We revisit the probabilistic construction of sparse random matrices whereeach column has a fixed number of nonzeros whose row indices are drawnuniformly at random. These matrices have a one-to-one correspondence with theadjacency matrices of lossless expander graphs. We present tail bounds on theprobability that the cardinality of the set of neighbors for these graphs willbe less than the expected value. The bounds are derived through the analysis ofcollisions in unions of sets using a {\em dyadic splitting} technique. Thisanalysis led to the derivation of better constants that allow for quantitativetheorems on existence of lossless expander graphs and hence the sparse randommatrices we consider and also quantitative compressed sensing sampling theoremswhen using sparse non mean-zero measurement matrices.
展开▼
机译：我们重新研究稀疏随机矩阵的概率构造，其中每列具有固定数量的非零值，其行索引是随机均匀绘制的。这些矩阵与无损扩展图的邻接矩阵具有一一对应关系。对于这些图的邻居集的基数将小于期望值的可能性，我们给出了尾限。使用{\ em dyadic splitting}技术通过分析集合并集中的冲突来导出边界。这种分析导致了更好的常数的推导，该常数允许对存在无损扩展图时的定量定理，从而考虑稀疏的随机矩阵，并在使用稀疏非均值零测量矩阵时进行定量压缩感知采样定理。
展开▼
